Introduzione agli algoritmi e strutture dati: array ordinato e ricerca binaria

l'ultima volta avevamo parlato di inserimenti,ricerche e tutte le operazioni che si potevano fare su array e set, oggi invece andremmo a parlare di array ordinati, ricerca binaria e come migliora i tempi nella ricerca negli array ordinati e poi introdurremo il concetto di big O, per prima cosa incomincerei parlando degli array ordinati.

Array ordinati

un array ordinato è identico ad un array classico se non per il fatto che deve essere mantenuto in ordine ogni qual volta viene inserito un nuovo elemento e quindi se per esempio abbiamo l’array 3,17,80,202 e inseriamo il valore 34, se avessimo una array normale potremmo inserire alla fine dell’array il valore in un solo passaggio invece visto che è ordinato prima di inserire il valore dobbiamo confrontare il valore che vogliamo inserire con i valori presenti all’interno dell’array in modo tale che da metterlo nella giusta posizione che mantenga l’ordinamento, quindi 34 andrà al indice 2 nel nostro array, quindi come possiamo notare quando eseguiamo un inserimento in un array ordinato dovremmo eseguire per forza una ricerca e quindi questo rappresenta una importante differenza prestazionale fra l'array normale e quello ordinato, quindi inizialmente nel array c'erano quattro elementi e per inserire un elemento ci abbiamo impiegato 6 passaggi, quindi possiamo dire che per N elementi in un array ordinato, l'inserimento ha richiesto N+2 passaggi in totale.

Un'altra cosa interessante da notare è che il numero di passaggi per l'inserimento rimane simile indipendentemente dal punto in cui finisce il nostro nuovo valore nell'array ordinato poichè se il nostro valore finisce verso l'inizio dell'array avremmo meno confronti e più spostamenti mentre se finisce alla fine avremmo più confronti e meno spostamenti. Il caso migliore lo avremmo proprio quando il valore finisce alla fine poichè eseguiremo N passaggi per confrontare il valore con gli altri valori dell'array e poi un passaggio per l'inserimento stesso, per un totale di N + 1 passaggi.

Passare dalla ricerca lineare a quella binaria

fino ad adesso abbiamo sempre visto la ricerca lineare come l'unico metodo per cercare in un array ordinato ordinato o no, quindi ogni volta dovevi andare a cercare in un array di n elementi facendo al massimo N ricerche per N elementi, ma quello che non sai è che esiste una ricerca assai potente che ci permetterà di avere delle ricerche molto ma molto più veloci.

Ricerca binaria

per applicare la ricerca binaria ad un array ordinato, supponendo di avere un array ordinato da 9 elementi e vogliamo inserire il valore 9 avremmo che:

1. inizieremmo la nostra ricerca dalla cella centrale e possiamo conoscere il valore della cella centrale poichè possiamo calcolare l'indice come la lunghezza dell'array diviso 2, quindi se supponiamo che il valore centrale sia 12, sapremmo già che tutti i valori dopo il 12 e il 12 stesso sono esclusi e quindi abbiamo già scartato metà dell'array.
2. poi dopo dall'array risultante prendiamo sempre la metà e rifacciamo lo stesso passaggio del punto uno ovvero il valore al centro per esempio sarà 6, allora sapremmo che potremmo scartare tutti i valori prima del 6 e il 6 stesso.
3. poi reiteriamo lo stesso passaggio un altra volta finchè non troviamo il valore che cerchiamo.

Ovviamente la ricerca binaria è possibile solo nel caso di un'array ordinato poichè per un array normale non sapremmo se effettivamente a destra di un valore ci sta un valore sicuramente più grande.

volendo fare un riassunto per array di piccole dimensioni come quello di prima, la ricerca binaria non è molto efficiente però nel momento in cui per esempio avremmo un array con 100 elementi possiamo notare che:

• la ricerca lineare ci metterà 100 passaggi poichè ci mette n passaggi per n elementi
• mentre la ricerca binaria ci mettera 7 passaggi per 100 elementi.

da cui si può intuire come man mano che il numero di elementi cresce la ricerca binaria diventa sempre più efficiente, poichè si dice che per ogni volta che raddoppiamo i dati, l'algoritmo di ricerca binaria aggiunge solo un ulteriore passaggio.

ora introdurremo un argomento molto importante ovvero il concetto di notazione Big O.

La Notazione Big O

la notazione Big O è una notazione presa in prestito dalla matematica, che serve a rispondere a una domanda chiave ovvero per N elementi di dati quanti passaggi richiederà l’algoritmo? prendendo come esempio la ricerca lineare avremmo che l’algoritmo sarà O(N) e quindi diremmo che l’algoritmo richiederà N passaggi, quindi quale è la risposta alla domanda di prima? sta nelle parentesi dopo la O ovvero quella N.

Oppure per esempio se dobbiamo fare una lettura da un’array diremmo che l’algoritmo lo esprimeremo come O(1) e quindi la risposta alla domanda principale di Big O cioè per N elementi di dati quanti passaggi richiederà l’algoritmo? diremmo che per N elementi richiederà sempre un solo passaggio poichè il numero di passaggi non varia al variare degli elementi. O(1) è considerato l’algoritmo più veloce e viene detto algoritmo a tempo costante

volendo fare un altro esempio di Big O prenderemo la ricerca binaria su un array ordinato e diremmo che l’efficienza della ricerca binaria in termini di notazione Big O, è un qualcosa che si piazza in mezzo tra O(1) e O(N) poichè al raddopiare dei dati aumenta di un solo passaggio non può essere definito ne algoritmo a tempo costante ne O(N) poichè i passaggi non aumentano al aumentare delle dimensioni dell’array ma aumenta di uno al raddoppiare delle dimensioni dell’array.